package search

import (
	"fmt"
	"math/rand"
	"time"
)

// Menu ,[2 ,7 ,9 ,14 ,19 ,21 ,34]
func Menu() {
	var arr []int
	flag1 := true
	for flag1 {
		fmt.Println("需要手动输入数组输入：y 自动生成数组输入: n")
		var ch string
		_, err := fmt.Scan(&ch)
		if err != nil {
			return
		}
		// 选择数组生成方式
		switch ch {
		case "y":
			arr = buildArray()
			flag1 = false
		case "n":
			arr = creatDisorderArray()
			flag1 = false
		default:
			fmt.Println("输入无效字符!")
		}
	}

	flag := true
	for flag {
		printDirectory()
		var number int
		_, err := fmt.Scan(&number)
		if err != nil {
			return
		}

		switch number {
		case 1:
			fmt.Printf("未排序:%d 升序:%d 降序:%d 先升序再降序:%d 先降序再升序:%d\n", 0, 1, 2, 3, 4)
			if checkArrUp(arr) {
				fmt.Println(1)
			} else if checkArrDown(arr) {
				fmt.Println(2)
			} else if checkArrUpToDown2(arr) {
				fmt.Println(3)
			} else if checkArrDownToUp2(arr) {
				fmt.Println(4)
			} else {
				fmt.Println(0)
			}
		case 2:
			fmt.Println("请输入要查找的元素: ")
			var num int
			_, err := fmt.Scan(&num)
			if err != nil {
				return
			}
			index, times := sequentialSearch(arr, num)
			if index != -1 {
				fmt.Printf("查找到目标元素:%d 位置下标:%d 比较次数:%d", num, index, times)
			} else {
				fmt.Printf("未查找到目标元素:%d 比较次数:%d", num, times)
			}
		case 3:
			fmt.Println("请输入要查找的元素: ")
			var num int
			_, err := fmt.Scan(&num)
			if err != nil {
				return
			}

			// 顺序查找
			index1, times1 := sequentialSearch(arr, num)
			if index1 != -1 {
				fmt.Printf("顺序查找(找到) -> 比较次数:%d 位置下标:%d\n", times1, index1)
			} else {
				fmt.Printf("顺序查找(未找到) -> 比较次数:%d\n", times1)
			}
			// 二分查找
			index2, times2 := binarySearch(arr, num)
			if index2 != -1 {
				fmt.Printf("二分查找(找到) -> 比较次数:%d 位置下标:%d\n", times2, index2)
			} else {
				fmt.Printf("二分查找(未找到) -> 比较次数:%d\n", times2)
			}
			// 三分查找
			index3, times3 := thirdSearch(arr, num)
			if index3 != -1 {
				fmt.Printf("三分查找(找到) -> 比较次数:%d 位置下标:%d\n", times3, index3)
			} else {
				fmt.Printf("三分查找(未找到) -> 比较次数:%d\n", times3)
			}
			// 插入查找
			//index4, times4 := interpolationSearch(arr, num)
			index4 := interpolationSearch2(arr, num, 0, len(arr)-1)
			times4 := timesInsert
			if index4 != -1 {
				fmt.Printf("插入查找(找到) -> 比较次数:%d 位置下标:%d\n", times4, index4)
			} else {
				fmt.Printf("插入查找(未找到) -> 比较次数:%d\n", times4)
			}
		case 4:
			max1, times1 := binaryGetMax(arr)
			fmt.Printf("二分查找 -> 最大值为:%d 比较次数:%d\n", max1, times1)
			max2, times2 := trisectionSearchMax(arr)
			fmt.Printf("三分查找 -> 最大值为:%d 比较次数:%d\n", max2, times2)
		case 5:
			// 生成一个随机数组，大小为10
			array := creatDisorderArray()
			fmt.Println("\n数组长度为10，请输入要查找的第k小的元素: ")
			var num int
			_, err := fmt.Scan(&num)
			if err != nil {
				return
			}
			if num <= len(array) {
				v, t := bruteForce(array, num)
				fmt.Printf("\n蛮力法 -> 第%d个最小的数为:%d 比较次数:%d\n", num, v, t)

				v1, t1 := preSort(array, num)
				fmt.Printf("预排序 -> 第%d个最小的数为:%d 比较次数:%d\n", num, v1, t1)

				v2, t2 := subtractVariableSize(array, num)
				fmt.Printf("减可变规模 -> 第%d个最小的数为:%d 比较次数:%d\n", num, v2, t2)
			} else {
				fmt.Println("k大于数组长度!")
			}
		case 0:
			flag = false
		default:
			fmt.Println("请输入正确的数字!")
		}
	}
}

func printDirectory() {
	fmt.Println("\n-----------\n----------请输入相应数字执行相应方法:")
	fmt.Printf("----------1. 判断数组的状态。\n" +
		"----------2. 使用顺序检索算法判断数字 x 是否在数组中。\n" +
		"----------3. 使用多种方法判断数字 x 是否在数组中。(需要数列有序)\n" +
		"----------4. 求先升后降数列最大值。\n" +
		"----------5. 使用多种方法查找数组中第k个最小元素。\n" +
		"----------0. 退出程序。\n----------")
}

func buildArray() []int {
	fmt.Println("请输入数组的长度:")
	var number int
	_, err := fmt.Scan(&number)
	if err != nil {
		fmt.Println(err.Error())
	}

	array := make([]int, number)
	for i := 0; i < number; i++ {
		fmt.Printf("请输入元素%d:", i+1)
		_, err := fmt.Scan(&array[i])
		if err != nil {
			fmt.Println(err.Error())
		}
	}

	// 打印数组
	fmt.Print("数组 [")
	for k, v := range array {
		if k == number-1 {
			fmt.Print(v, "]")
		} else {
			fmt.Print(v, " ,")
		}
	}
	return array
}

func creatDisorderArray() []int {
	numbers := make([]int, 10)
	//t1 := time.Now()
	// 设置种子数，可以设置时间戳
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < 10; i++ {
		// 调用生成随机数的函数
		numbers[i] = rand.Intn(100)
	}

	// 打印数组
	fmt.Print("数组 [")
	for k, v := range numbers {
		if k == 9 {
			fmt.Print(v, "]")
		} else {
			fmt.Print(v, " ,")
		}
	}
	return numbers
}
